/**
 * SmallestNumberNerverAppear.java created by zhangzhidong 
 * at 下午8:27:14 2015年10月6日
 */
package newcoder.algorithm;

/**
 * @author zhangzhidong
 *
 *
 *数组中未出现的最小正整数
【题目】
给定一个无序整型数组arr，找到数组中未出现的最小正整数。 
【举例】
arr=[-1,2,3,4]。返回1。
arr=[1,2,3,4]。返回5。
 */
import static util.Utils.swap;
public class SmallestNumberNerverAppear {

	/**
	 * 下午8:27:14 2015年10月6日
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(algorithm(new int[]{-1,2,3,4,}));
	}
	public static int algorithm(int []arr){
		int l = 0;
		int r=arr.length;
		while(l<r){
			if(arr[l]==l+1){
				l++;
			}else if(arr[l]<l+1 || arr[l]>r || arr[arr[l]-1]==arr[l]) {
				
				arr[l]=arr[--r];
			}else {
				swap(arr,l,arr[l]-1);
			}
		
		}
		return l+1;
	}
	
	

}
